package com.excise01;

/**
 * Created by 54416 on 2017/5/20.
 */

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 翻译：
 给定一个整形数组和一个整数target，返回2个元素的下标，它们满足相加的和为target。
 你可以假定每个输入，都会恰好有一个满足条件的返回结果。
 */

public class Solution {
    //第一种方法，时间复杂度是O（n^2）
    public int[] twoSum(int[] nums, int target){
        int first=0;
        int second=0;
        for(int i=0; i<nums.length-1;i++){
            for (int j=i+1; j<nums.length; j++){
                if (nums[i] + nums[j] == target){
                  first=i;
                  second=j;
                  break;
                }
            }
        }
        return new int[]{first,second};
    }

    //第二种方法参考其他人的，时间复杂度是O（n）
    public int[] twoSum2(int[] nums,int target){
        Map<Integer, Integer> hashMap = new HashMap<>();
        for (int i=0; i<nums.length; i++){
            Integer index = hashMap.get(target - nums[i]);
            System.out.println(index);
            if (index == null){
                hashMap.put(nums[i],i);
            }else {
                System.out.println(hashMap);
                return new int[]{i,index};
            }
        }
        return new int[]{0,0};
    }


    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] numbers = {10,20,50,60,70};
        int[] result;
        result = solution.twoSum(numbers,8);
        System.out.println(Arrays.toString(result));
        //输出数组的方法是 Arrays.toString()
        //System.out.println(Arrays.toString(new int[]{1,2}));

        int[] result2 = solution.twoSum2(numbers, 120);
        System.out.println(Arrays.toString(result2));

    }
}


